Lexicographical order Totally Explained

Everything about Lexicographic Order totally explained

In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets. Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as ť (a,b) ≤ (a′,b′) if and only if a ≤ a′ or (a = a′ and b ≤ b′).

The result is a partial order. If A and B are totally ordered, then the result is a total order also.
More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

Motivation and uses

The name of the lexicographic order comes from its generalizing the order given to words in a dictionary: a sequence of letters (that is, a word) ť a₁a₂ ... a_k

appears in a dictionary before a sequence ť b₁b₂ ... b_k

if and only if the first a_i which is different from b_i comes before b_i in the alphabet. That assumes both have the same length; what is usually done is to pad out the shorter word with symbols for 'blanks', and to consider that a blank is a new minimum ('bottom') element.
   For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases. See alphabetical order.
   An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.
   An important exploitation of lexicographical ordering is expressed in the ISO 8601 date formatting scheme, which expresses a date as YYYY-MM-DD. This date ordering lends itself to straightforward computerized sorting of dates such that the sorting algorithm doesn't need to treat the numeric parts of the date string any differently from a string of non-numeric characters, and the dates will be sorted into chronological order. Note, however, that for this to work, there must always be four digits for the year, two for the month, and two for the day, so for example single-digit days must be padded with a zero yielding '01', '02', ..., '09'.

Case of multiple products

Suppose ť

has no least element: ... <

^d aab <^d ab <^d b. A well-order for strings, based on the lexicographical order, is the shortlex order. Similarly we can also compare a finite and an infinite string, or two infinite strings. Comparing strings of different lengths can also be modeled as comparing strings of infinite length by right-padding finite strings with blank spaces, if, as usual, the blank space is the least element of the alphabet (or, if it's originally not in the alphabet, adding it as least element).

Generalization

Consider the set of functions f from a well-ordered set X to a totally ordered set Y. For two such functions f and g, the order is determined by the values for the smallest x such that f(x) ≠ g(x). If Y is also well-ordered and X is finite, then the resulting order is a well-order. As already shown above, if X is infinite this is in general not the case. If X is infinite and Y has more than one element, then the resulting set Y^X isn't a countable set, see also . Alternatively, consider the functions f from an inversely well-ordered X to a well-ordered Y with minimum 0, restricted to those which are non-zero at only a finite subset of X. The result is well-ordered. Correspondingly we can also consider a well-ordered X and apply lexicographical order where a higher x is a more significant position. This corresponds to Y^X. If X and Y are countable then the resulting set is also countable.

Monomials

In algebra it's traditional to order terms in a polynomial, by ordering the monomials in the indeterminates. This is fundamental, in order to have a normal form. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by ť X < Y < ... and also to look at higher terms first, that means ordering ť ... < X³ < X² < X and also ť X < Y^k for all k. There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis theory.

Decimal fractions

For from the decimal point, a < b applies equivalently for the numerical order and the lexicographic order, provided that numbers with a recurring decimal 9 like .399999... are not included in the set of strings representing numbers. With that restriction there's an order-preserving bijection between the strings and the numbers.

Lexicographic order with reversed significance

In a common variation of lexicographic order, one compares elements by reading from the right instead of from the left, for example, the right-most component is the most significant, for example applied in a rhyming dictionary. In the case of monomials one may sort the exponents downward, with the exponent of the first base variable as primary sort key, for example: ť

x^2 y z^2 < x y^3 z^2

.

Alternatively, sorting may be done by the sum of the exponents, downward.

Further Information

Get more info on 'Lexicographic Order'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://lexicographical_order.totallyexplained.com">Lexicographical order Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.